#include <iostream>
using namespace std;
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity; 
}Heap;

void HeapInit(Heap* php) {
    php->_a = nullptr;
    php->_size = 0;
    php->_capacity = 0;
}
// 堆的销毁
void HeapDestory(Heap* hp) {
    free(hp->_a);
    hp->_a = nullptr;
    hp->_capacity = 0;
    hp->_size = 0;
}
// 向上调整
void AdjustUp(HPDataType* _a, int n) {
    int parent = (n - 1) / 2;
    while(n > 0 && _a[n] > _a[parent]) {
        HPDataType temp = _a[parent];
        _a[parent] = _a[n];
        _a[n] = temp;
        n = parent;
        parent = (n - 1) / 2;
    }
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x) {
    if(hp->_capacity == hp->_size) {
        int temp = hp->_capacity == 0 ? 4 : 2 * hp->_capacity;
        hp->_a = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * temp);
        hp->_capacity = temp;
    }
    hp->_a[hp->_size++] = x;
    AdjustUp(hp->_a, hp->_size - 1);
}
// 向下调整算法
void AdjustDown(HPDataType* _a, int n, int parent) {
    int child = (parent * 2 + 1); // 计算儿子节点
    while(child < n) // 循环条件
    {
        if(child + 1 < n && _a[child] < _a[child + 1]) // 找到更大的那一个
        {
            child++;
        }
        if(_a[child] > _a[parent]) // 交换对应的值
        {
            HPDataType temp = _a[parent];
            _a[parent] = _a[child];
            _a[child] = temp;
            parent = child;
            child = (parent * 2 + 1);
        }else // 条件不满足退出即可（注意）
        {
            break;
        }
    }
}
// 堆的删除
void HeapPop(Heap* hp) {
    if(hp->_size == 0) return;
    HPDataType temp = hp->_a[0];
    hp->_a[0] = hp->_a[hp->_size - 1];
    hp->_a[hp->_size - 1] = temp;
    hp->_size--;
    AdjustDown(hp->_a, hp->_size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp) {
    return hp->_a[0];
}   
// 堆的数据个数
int HeapSize(Heap* hp) {
    return hp->_size;
}
// 堆的判空
int HeapEmpty(Heap* hp) {
    return hp->_size == 0;
}
// 堆排序算法
void HeapSort(int* a, int n) {
    for(int i = (n - 2) / 2; i >= 0; i--) {
        AdjustDown(a, n, i);
    }
    for(int end = n - 1; end > 0; end--) {
        int temp = a[0];
        a[0] = a[end];
        a[end] = temp;
        AdjustDown(a, end, 0);
    }
}
// int main() {
//     Heap hp;
//     HeapInit(&hp);

//     HeapPush(&hp, 10);
//     HeapPush(&hp, 20);
//     HeapPush(&hp, 5);

//     printf("堆顶: %d\n", HeapTop(&hp)); // 输出 20（大根堆）

//     HeapPop(&hp);
//     printf("新的堆顶: %d\n", HeapTop(&hp)); // 输出 10

//     HeapDestory(&hp);
//     return 0;
// }

// int main()
// {
//     int arr[] = {3, 1, 5, 2, 4, 6, 8, 7, 9};
//     int n = sizeof(arr) / sizeof(arr[0]);

//     HeapSort(arr, n);

//     for (int i = 0; i < n; i++)
//         printf("%d ", arr[i]);

//     return 0;
// }

